[NOIP2007]-树网的核

树的直径

传送门

题意：说不清。。。看原题吧?

NOIP 数据可以直接上朴素算法，$O(n^3)$ 。首先通过两次 BFS 或 DFS 求出树的直径，然后在直径上枚举距离不超过 $s$ 的两个点 $p$ 和 $q$ ，$p$、$q$ 之间的路径就是树网的核。先将核上的每个节点标记为“已访问”，然后从核上的每个节点出发，执行深搜，求出偏心距最大值即为偏心距。

稍加观察，$p$、$q$ 之间的距离肯定是越大越好，所以只要枚举 $p$ 就行了，$q = p + s$。 $O(n^2)$ 。

然鹅这样还是过不了 BZ 的数据。。

发现，本题的答案具有单调性，可以二分答案，把问题转化为“验证是否存在一个核，其偏心距不超过二分的值 $mid$” 。

设直径的两个端点为 $u$ 和 $v$ ，在直径上找到与 $u$ 的距离不超过 $mid$ 的前提下，距离最远的节点，作为节点 $p$。类似地找到与 $v$ 的距离不超过 $mid$ 的前提下，距离最远的节点，作为节点 $q$。

根据直径的最长性（标黑加粗！），任何从 $u$、$p$ 之间分叉离开直径的子树，其最远点与 $p$ 的距离都不会比 $u$ 更远。所以 $p$、$q$ 就是满足直径两侧的那部分节点偏心距不超过 $mid$ 的前提下、尽量靠近树网中心的节点。

接下来就是检查 $p$、$q$ 的距离是否不超过 $$s ，同时用深搜检查离核最远的点的距离是否也不超过 $s$。如果两个条件都满足，$p$、$q$ 之间的路径就是偏心距不超过 $mid$ 的一个合法的核。

该算法 $O(n log SUM)$ ，其中 $SUM$ 表示树网所有边的长度之和。

据说还有一个 $O(n)$ 的算法。算出 $d[u_i]$ ，表示从每一个直径上的节点 $u1$ ~ $ut$ ，不经过直径上的其他节点，能够到达的最远点的距离。

所以实际上答案是：

由于直径的最长性（标黑加粗！），上式其实可简化为：

$max_{1 \leq k \leq t}\{d[u_k]\}$ 是定值，可以直接算出。

所以最后只要用指针计算后两项，单调递增，$O(n)$ ！！

所以说，算法从某种程度上，设计、优化是永无止境的啊，一定要多动脑，不要满足于AC。

$O(n log SUM)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
int n, s, cnt, fa[N], fc[N], dep[N], idx[N], sum[N];
bool used[N];
struct edge {int to, val;};
vector<edge> nxt[N];
queue<int> q;

void bfs() {
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)nxt[u].size(); i++) {
            if (dep[nxt[u][i].to] < 0) {
                dep[nxt[u][i].to] = dep[u] + nxt[u][i].val;
                fa[nxt[u][i].to] = u, fc[nxt[u][i].to] = nxt[u][i].val;
                q.push(nxt[u][i].to);
            }
        }
    }
}

int find_dia(int x) {
    memset(dep, -1, sizeof(dep));
    q.push(x), dep[x] = 0;
    bfs();
    for (int i = 1; i <= n; i++) {
        if (dep[x] < dep[i]) x = i;
    }
    return x;
}

bool check(int x) {
    int l = 1, r = cnt;
    for (int y = x; l < cnt && y >= sum[l + 1] - sum[l]; l++)
        y -= sum[l + 1] - sum[l];
    for (int y = x; r > 1 && y >= sum[r] - sum[r - 1]; r--)
        y -= sum[r] - sum[r - 1];
    return sum[r] - sum[l] <= s;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        nxt[u].push_back((edge){v, w}), nxt[v].push_back((edge){u, w});
    }
    int s = find_dia(1), t = find_dia(s), k = t;
    for (idx[++cnt] = k; k != s; k = fa[k]) {
        idx[++cnt] = fa[k], sum[cnt] = sum[cnt - 1] + fc[k];
    }
    int l = 0, r = dep[t];
    memset(dep, -1, sizeof(dep));
    for (int i = 1; i <= cnt; i++) q.push(idx[i]), dep[idx[i]] = 0;
    bfs();
    for (int i = 1; i <= n; i++) l = max(l, dep[i]);
    while (l < r) {
        int mid = (l + r) >> 1;
        if (!check(mid)) l = mid + 1;
        else
            r = mid;
    }
    cout << l << endl;
    return 0;
}